CS100 Final Exam Cover Sheet

Instructors: Laurent Kneip, Jie Zheng, Fu Song

January 16, 2019

INSTRUCTIONS:

You have 110 minutes (09:10-11:00) to complete the exam.
Your exam will not be graded unless you complete the above section and the cover sheet, and turn in both this exam book and the cover sheet.
This exam is closed-book and closed-notes, and no electronic devices are permitted.
Mark your answers on the exam itself. We will not grade answers written on scratch paper.
Your performance is supposed to reflect your own level of understanding of the material. You are not allowed to talk with your neighbor or look at his exam sheet. Failure to obey this rule will simply result in a zero score.
If you finish early, you can hand in the exam and leave early. However, this is only possible until at latest 15 minutes before the ending time of the exam. If less than 15 minutes are left, please stay seated and wait for the end.

Problem 1: Multiple-choice questions (12 points)

Please answer the following questions by ticking the choices that apply. Each question has 1 point, and is clearly marked as a C, C++, or Python question. Note that multiple choices are possible for each question. Mark all possible choices that apply by ticking the corresponding box.

Question 1 (C)

?/? point (graded)

Assuming a 3-dimensional array is declared as int ar[5][4][3], what is the correct syntax to send the 3-dimensional array as a parameter to a function F( )?

Question 2 (C)

?/? point (graded)

What will be the output of the following C code, supposing that the corresponding executable file is run without any command line argument.


#include <stdio.h>
int main(int argc, char *argv[])
{
    while (argc--) { 
        printf(“%s\n”, argv[argc]);
    }
    return 0;
}

Question 3 (C)

?/? point (graded)

Consider the following declaration statement in C:

int *ptr, p;

Choose all of the following statements that are not correct!

Question 4 (C)

?/? point (graded)

What will be the output of the following C code?


#include <stdio.h>
int main(void)
{
    int a = 5;
    int *p = &a;
    int **q = &p;
    (**q)++;
    printf("%d\n", a);
    return 0;
}

Question 5 (C++)

?/? point (graded)

Polymorphism is a programming concept that may …

Question 6 (C++)

?/? point (graded)

The default constructor …

Question 7 (C++)

?/? point (graded)

The data inside a std::map is …

Question 8 (C++)

?/? point (graded)

Concurrency: Mark all statements that apply

Question 9 (Python)

?/? point (graded)

What will be the output of the following Python code?


x = 2
def foo():
    x = 3
    def bar():
        x = 4
        return lambda z: x+z 
    return lambda z:bar()(x*z)
print(foo()(x))

Question 10 (Python)

?/? point (graded)

What will be the Method Resolution Order (MRO) of the class C4 in the following Python code?


class C1:
    def foo(self):
        print(1)

class C2(C1):
    None
class C3():
    def foo(self):
        print(3)

class C4(C2,C3):
    None

Question 11 (Python)

?/? point (graded)

What will be the Method Resolution Order (MRO) of the class C4 in the following Python code?


def foo(a,b):
    s = 0
    try:
        s = s + bar(a,b)
        s = s + 10
    except ZeroDivisionError: 
        s = s + 20
    else: 
        s = s + 30 
    finally: 
        s = s + 40
    return s

def bar(a,b): 
    s = 0 
    try:
        a//b
        s = s + 1
    except ZeroDivisionError: 
        s = s + 2
    else: 
        s = s + 3 
    finally: 
        s = s + 4 
    return s

print(foo(1,0)+foo(1,1))

Question 12 (Python)

?/? point (graded)

Choose all the function definitions that are correct in Python?

Problem 2: Find and correct problems and bugs (14 points)

Question 1 (C, 4 points)

?/? point (graded)

Find 4 lines with errors in the following C code. State the line numbers to indicate errors. In addition, for each line number, briefly explain what the error is, and propose a correct replacement statement. Note: There could be more than 4 lines with errors, but you only need to find and correct 4 of them.
(Due to the limitation of the website, you just need to submit line number of the potential bug.)


/* The following C program processes an array of student records. For each record, it stores the student’s id and name. In the program, it reads each student’s information, and then prints the student information. The functions input() and output() are used for the reading and printing of student information. */

1	#include <stdio.h>
2	#define SIZE 10
3	struct Student {
4	    int id;
5	    char name[10];
6	};
7	void input(struct Student s);
8	void output(struct Student s);
9	int main() {
10	    struct Student s[SIZE];
11	    int i;
12	    for (i=0; i < SIZE; i++)
13	    input(s[i]);
14	    for (i=0; i < SIZE; i++)
15	        output(s[i]);
16	    printf(“\n”);
17	    return 0;
18  }
19	void input(struct Student s) {
20	    printf(“Student ID: ”);
21	    scanf(“%d”, &s.id);
22	    printf(“Student Name: ”);
23	    scanf(“%s”, s.name);
24  }
25	void output(struct Student s) {
26	    printf(“%s(%d) ”, s.name, s.id); 
27  }

Please type in the line numbers of the potential bugs. Just the number is okay. (Each box one number)

Answer

Error 1:

Line 7. The argument s should be a pointer to a structure of “Student”, in order to retrieve the data input by user through call by reference. So the corrected statement is:
void input(struct Student *s);
Error 2:
Line 19. Similar to Error 1, the argument should be a pointer to a structure variable. Thus, the corrected statement should be:
void input(struct Student *s) {
Error 3:
Line 21. Since s is a pointer to structure, s.id should be changed to s->id to access the member of the structure. Hence, the corrected statement is:
scanf(“%d”, &(s->id));
Error 4:
Line 23. Similar to Error 3, since s is a pointer to structure, “s.name” should be replaced by “s->name”. Thus, the corrected statement should be:
scanf(“%s”, s->name);
Error 5:
Line 13. The input() function accepts a pointer to structure as its argument, hence the parameter should be the address to the ith element of the array s. Hence, the corrected statement should be:
input(&s[i]);

Question 2 (C++, 4 points)

?/? point (graded)

Find two problems in the following C++ code. Mention the relevant line, provide an explanation to the problem, and propose a solution.
(Due to the limitation of the website, you just need to submit line number of the potential bug.)


1	class IntegerArray {
2	public:
3	    int *m_data;
4	    int m_size;
5
6	    IntegerArray(int size) {
7	        m_data = new int[size];
8	        m_size = size;
9	    }
10
11	    ~IntegerArray() {} 
12  };
13
14	int main() {
15	    IntegerArray a(2);
16	    a.m_data[0] = 4; a.m_data[1] = 2;
17	    if (true) {
18	        IntegerArray b = a;
19	        b.m_data[0] = 6;
20	    }
21	    printf("%d\n", a.m_data[0]);
22 }

Please type in the line numbers of the potential bugs. Just the number is okay. (Each box one number)

Answer

Error 1:
Line 18: The copy constructor is invoked, which is however not implemented. The default copy constructor does not make a deep copy, which is why Line 19 will unintentionally change the original.
Solution: add the copy constructor:
IntegerArray( IntegerArray & op) { 
    m_data = new int[op.m_size]; 
    m_size = op.m_size;
    for( int i = 0; i < m_size; i++ ) 
        m_data[i] = op.m_data[i];
}
                                            
Error 2:
Line 11: The destructor is empty and fails to delete the allocated array. The addition of the copy constructor is also motivated by this error, as deleting the array in the destructor would otherwise delete the original upon destruction of b, and thus produce a segmentation fault in Line 21.
Solution: free the allocated space in the destructor
~IntegerArray() { 
    delete[] m_data;
}
                                            

Question 3 (Python, 6 points)

?/? point (graded)

Find 6 errors in the following Python code. For each error, indicate the line number, briefly explain what the error is, and correct the statements. Note: There might be more than 6 errors, but you only need to find and correct 6 of them. The program is a grade evaluation program. It first reads and stores each student’s name and score of an exam, then computes the average score of all scores, and finally stores the average score in each student’s information.
(Due to the limitation of the website, you just need to submit line number of the potential bug.)


1  def GetStudentsInfor(L = []):
2      '''Get all students' names and scores'''
3      for i in range(1,100):
4      L.append(GetOneStudentInfor())

5  def GetOneStudentInfor():
6      '''Get one student name and score'''
7      name = input("Please input name:")
8      score = input("Please input score:")
9      return (name,score)

10 def ComputeAverageScore(L):
11     '''Compute the arithmetic average of all students' scores'''
12     totalScore = sum( s[-1] for s in L)
13     averageScore = totalScore/100
14     return averageScore

15 def AddAverageScore(L,averageScore):
16     '''Add the average Score into each student's information'''
17     for i in L:
18         i.append(averageScore)

19 def GetInfor(L,studentName):
20     '''Get information of a student whose name is studentName'''
21     for i in L:
22         if i[0] is studentName:
23             return i
24 L = List()
25 GetStudentsInfor(L)
26 aver = ComputeAverageScore(L)
27 AddAverageScore(L,aver)
28 print(GetInfor(L,"foo"))

Please type in the line numbers of the potential bugs. Just the number is okay. (Each box one number)

Answer

Error 1: The number of students is inconsistent at Line 3 and Line 13. Replace either “range(1,100)” at Line 3 by one of “range(100)”, “range(0,100)”, “range(1,101)”, etc, or replace “100” at Line 13 by “99”.
Error 2: unexpected indent at Line 7. Remove some space at the begin of Line 7 such that Lines 6-7 are have same white space and the number of white spaces is greater than zero.
Error 3: Line 8 or Line 9 or Line 12. The type of score is str which should be int. Rewrite “score = input("Please input score:")” at Line 8 by “score = int(input("Please input score:") )”, or “score” at Line 9 by “int(score)” , or “s[-1]” at Line 12 by “int(s[-1])”.
Error 4. At Line 9 “(name,score)” cannot be a tuple, it should be a list “[name,score]”.
Error 5. “is” at Line 22 should be “==”. “is” compares whether two objects are same, rather than whether two strings are same.
Error 6. Line 24, “L = List()” should be “L = list()” or “L=[]”. Python is case sensitive.

Problem 3: C problem (C, 4 points)

Write a recursive C function countZeros() that counts the number of zeros in a specified positive integer num. Assume that the left-most (also known as the most significant) digit is non-zero. The function passes the result to the caller through the parameter count, which is a pointer to an integer that is initialized to 0. For example, countZeros(150060, count) returns 3 and countZeros(15867, count) returns 0. The function prototype is given as follows:


void countZeros(int num, int *count);

Note: You do not need to write the function main() which would test the function countZeros().

Problem 4: C++ problem set (C++, 10 points)

Question 1 (C++, 4 points)

?/? point (graded)

Predict the output of the following code. What code changes are needed if we additionally want to print full-time employees first. Note: You do not need to copy the entire code, you only need to write the new ordering function!


#include <iostream>
#include <algorithm>

struct Employee {
public:
    std::string name, id; 
    bool isFulltime;
};

bool comparator( Employee * op1, Employee * op2 ) { 
    if( op1->id.size() != op2->id.size() ) {
        if( op1->id.size() < op2->id.size() ) 
            return true;
        return false;
    }
    return op1->id < op2->id;
}


int main() {

    Employee e1, e2, e3, e4;	
    e1.name = "Cindy";      e1.id = "20180915";     e1.isFulltime = false;
    e2.name = "Simon";      e2.id = "20180309";     e2.isFulltime = false;
    e3.name = "Jennifer";   e3.id = "370";          e3.isFulltime = true;
    e4.name = "Paul";       e4.id = "20181002";     e4.isFulltime = true;


    std::map<std::string,Employee*> staff;
    staff["Cindy"]      = &e1;  staff["Simon"]  = &e2;
    staff["Jennifer"]   = &e3;  staff["Paul"]   = &e4;

    std::vector<Employee*> reorderedStaff( staff.size() ); int i = 0; 
    for(	std::map<std::string,Employee*>::iterator it = staff.begin();
            it != staff.end(); it++ ) 
        reorderedStaff[i++] = it->second;

    std::sort( reorderedStaff.begin(), reorderedStaff.end(), comparator ); 
    for(	std::vector<Employee*>::iterator it = reorderedStaff.begin();
            it != reorderedStaff.end(); it++ )
        std::cout << (*it)->id << ": " << (*it)->name << std::endl;
    
    return 0;
}

Question 2: (C++, 6 points)

Propose a template class that generalizes the below two classes. Add a function that allows us to write the sum of two vectors using the expression

DoubleVector d3 = d1 + d2;

and not

DoubleVector d3 = d1.sum(d2);


class DoubleVector {
public:
    DoubleVector( int size ) {
        m_size = size;
        m_data = new double[size];
    }

    virtual ~DoubleVector() {
        delete[] m_data;
    }

    double & operator[] ( int index ) {
        return m_data[index];
    }

    DoubleVector sum( DoubleVector & op ) {
        DoubleVector result( this->m_size );
        for( int i = 0; i < this->m_size; i++ )
            result[i] = (*this)[i] + op[i];

        return result;
    }

private:
    double * m_data;
    int m_size;
};


class IntVector {
public:
    IntVector( int size ) {
        m_size = size;
        m_data = new int[size];
    }

    virtual ~IntVector() {
        delete[] m_data;
    }

    int & operator[] ( int index ) {
        return m_data[index];
    }

    IntVector sum( IntVector & op ) {
        IntVector result( this->m_size );
        for( int i = 0; i < this->m_size; i++ )
            result[i] = (*this)[i] + op[i];

        return result;
    }
    
private:
    int * m_data;
    int m_size;
};

Problem 5: Python problem (Python, 10 points)

Read the following Rational Class and gcd function.


def gcd(m, n):
    if n == 0: 
        m, n = n, m 
    while m != 0:
        m, n = n%m, m 
    return n

class Rational:
    def __init__(self, num, den = 1) : 
        if den == 0 : 
            raise ValueError 
        sign = 1
        if (num < 0) :
            num, sign = -num, -sign 
        if (den < 0) :
            den, sign = -den, -sign 
        g = gcd(num, den)
        self.num = sign * (num//g) 
        self.den = den//g
    def __str__(self) :
        return str(self.num) + "/" + str(self.den)

r = Rational(2,4) 
print(r)	# outputs 1/2

1) Write a function for the class Rational such that the following code outputs 18/65 (4 points)


x = Rational(2,26)
y = Rational(5,25)
print(x+y)

2) Write a function for the class Rational such that the following code outputs 1/5 (6 points)


x = Rational(2,26)
y = Rational(5,25)
print(x*y*13)

Additional Resources

The answer of the whole exam can be fond here.

The question sheet can be fond here.